import java.util.ArrayList;
import java.util.List;

/**
 * 把只包含因子2、3和5的数称作丑数（Ugly Number）。
 * 例如6、8都是丑数，但14不是，因为它包含因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * Created by Administrator on 2017/2/20.
 */
public class Test2 {

//    public int GetUglyNumber_Solution(int index) {
//        int num = 1;
//        int count = 0;
//        while (count != index) {
//            if (isUglyNumber(num)) {
//                count++;
//            }
//            num++;
//        }
//        return --num;
//    }
//
//    private boolean isUglyNumber(int num) {
//        while (num % 2 == 0) {
//            num = num / 2;
//        }
//
//        while (num % 3 == 0) {
//            num = num / 3;
//        }
//
//        while (num % 5 == 0) {
//            num = num / 5;
//        }
//
//        return num == 1;
//    }

    public int GetUglyNumber_Solution(int index) {
        if (index == 0) {
            return 0;
        }
        int[] arr = new int[index];
        arr[0] = 1;
        List<Integer> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        List<Integer> list5 = new ArrayList<>();
        for (int i = 0; i < index - 1; i++) {
            list2.add(arr[i] * 2);
            list3.add(arr[i] * 3);
            list5.add(arr[i] * 5);
            int temp = getMinNum(list2.get(0), list3.get(0), list5.get(0));
            if (list2.contains(temp)) {
                list2.remove(0);
            }

            if (list3.contains(temp)) {
                list3.remove(0);
            }

            if (list5.contains(temp)) {
                list5.remove(0);
            }
            arr[i + 1] = temp;
        }
        return arr[index - 1];
    }

    private int getMinNum(Integer m2, Integer m3, Integer m5) {
        int temp = m2 < m3 ? m2 : m3;
        return temp < m5 ? temp : m5;
    }


    public static void main(String[] args) {
        Test2 test2 = new Test2();
        int i = test2.GetUglyNumber_Solution(1500);
//        int i = test2.GetUglyNumber_Solution(1500);
        System.out.println(i);
    }
}
